/* 利用BFS求无向图的最短路径 */
#include <iostream>
#include "algraph.h"
using namespace std;

// 创建图 -- 邻接表
void BFSmin(ALGraph *G, int v, int d[])
{
  // 记录结点是否被访问过
  int visit[maxsize];
  
  // 记录初始结点到各个结点的最短路径
  for (int i = 0; i < G->numver; ++i)
    d[i] = INT16_MAX; 
  
  // 初始时，各个结点均未被访问
  for (int i = 0; i < G->numver; ++i)
    visit[i] = 0;
  
  // 创建辅助队列
  int que[maxsize];
  int front = 0, rear = 0;
  
  // 访问初始结点
  visit[v] = 1;
  
  // 距离为0
  d[v] = 0;
  
  // 初始结点进队列
  que[++rear] = v;
  
  // 队列不为空
  while (front != rear)
  {
    // 结点出队
    int v = que[++front];
    
    // 读取邻接结点
    ArcNode *p = G->adjlist[v].firstarc;
    
    // 邻接结点不为空
    while (p != NULL)
    {
      // 邻接结点未被访问
      if (visit[p->adjvex] == 0)
      {
        // 更新最短路径
        d[p->adjvex] = d[v] + 1;
        
        // 更新访问标记
        visit[p->adjvex] = 1;
        
        // 进队
        que[++rear] = p->adjvex;
      }
      
      // 到达下一个邻接结点
      p = p->nextarc;
    }
  }
}

int main()
{
  // 创建图 -- 邻接表
  ALGraph *G = create_algraph(4, 4);
  
  // 记录初始结点到各个结点的最短路径
  int d[maxsize];
  
  // 广度优先搜索，找最短路径长度
  BFSmin(G, 0, d);
  
  // 输出0号结点到3号结点到最短路径长度
  cout << d[3];
  return 0;
}